题目分析

这个题目是我在学习一维逆序对时，有一个同学提问二维逆序对如何求解时发现的，他说在面试某厂时，面试官提出的问题。我的天，现在的面试手撕代码已经这么BT了吗？一维逆序对还不行？？？我思考了一下，没写出来，因此也算是我自己的一个学习机会。

模拟

在一维的逆序对中，tree[x]表示连续lowBit(x)个元素之和。

在二维中是不是可以用tree[x][y]表示连续lowBit(x) x lowBit(y)个元素之和。

将数组进行从大到小排序，并从最大值开始遍历，遍历到某个元素时，如果左上方已经出现k个，那么该元素的逆序对是k个。

因为排序时要记录元素的值和下标，我们创建一种数据结构Element，用来保存数据。

排序时，如果两个元素的值相同，则按照x和y的索引从大到小排序，因为这样先遍历到的一定是索引大的，然后遍历到索引小的不会记录个数。

剩下的add和query方法就是和一维树状数组类似了。因此tree[x][y]记录的是array[x][y] + array[x - 1][y] + … array[x - lowBit(x) + 1][y] + array[x][y - 1] + array[x - 1][y - 1] + … + array[x - lowBit(x) + 1][y - 1] + … + array[x][y - lowBit(y) + 1] + array[x - 1][y - lowBit(y) + 1] + … + array[x - lowBit(x) + 1][y - lowBit(y) + 1]个元素之和。

不理解的小伙伴可以去参考逆序对，详细理解逆序对后，才能理解本题的解法。

综上所述，算法的时间复杂度为$O(mnlog(m)log(n))$，空间复杂度为$O(mn)$。

class Solution {
    private int row;

    private int col;

    private int[][] tree;

    private int reversedPair(int[][] array) {
        row = array.length;
        col = array[0].length;
        Element[] elements = new Element[row * col];
        int idx = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                elements[idx++] = new Element(array[i][j], i + 1, j + 1);
            }
        }
        Arrays.sort(elements, (o1, o2) -> {
            if (o1.val != o2.val) {
                return o2.val - o1.val;
            }
            if (o1.x != o2.x) {
                return o2.x - o1.x;
            }
            return o2.y - o1.y;
        });
        tree = new int[row + 1][col + 1];
        int res = 0;
        for (int i = 0; i < row * col; i++) {
            res += query(elements[i].x, elements[i].y);
            add(elements[i].x, elements[i].y);
        }
        return res;
    }

    private void add(int x, int y) {
        for (int i = x; i <= row; i += lowBit(i)) {
            for (int j = y; j <= col; j += lowBit(j)) {
                tree[i][j]++;
            }
        }
    }

    private int query(int x, int y) {
        int cnt = 0;
        for (int i = x; i > 0; i -= lowBit(i)) {
            for (int j = y; j > 0; j -= lowBit(j)) {
                cnt += tree[i][j];
            }
        }
        return cnt;
    }

    private int lowBit(int x) {
        return x & -x;
    }

    private static class Element {
        private int val;

        private int x;

        private int y;

        Element(int val, int x, int y) {
            this.val = val;
            this.x = x;
            this.y = y;
        }
    }
}

刷题总结

通过本题，我们又能对树状数组的理解加深一个层次。下面给小伙伴们出一些思考题，看下是否真正理解了逆序对。如果本题让你求每个元素左上方比它大的元素个数，返回一个二维矩阵，应该如何求解呢？如果是左上方大于等于该元素的个数又该如何求解呢？

返回二维矩阵，其实就是将query中的值保存下来，因为query的值，就是左上角大于该元素的数量。
如果是大于等于，那么就将排序的o2.x-o1.x，o2.y-o1.y改成o1.x-o2.x，o1.y-o2.y，小伙伴们可以思考思考其中的奥秘。